package com.jiang.daily.Q1387;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author Jiang
 * @version 1.0
 * @date 2024/12/22 21:27
 */
class Solution {
    public int getKth(int lo, int hi, int k) {
        // 根据Map集合的值进行排序
//        Map<Integer, Integer> map = new LinkedHashMap<>();
//        for (int i = lo; i <= hi; i++) {
//            map.put(i, getWeight(i));
//        }
//        map = map.entrySet().stream().sorted(Map.Entry.comparingByValue()).collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));
//        int cnt = 1;
//        for (Integer res : map.keySet()) {
//            if (cnt == k) return res;
//            cnt++;
//        }
//        return 0;

//         根据List集合进行排序
//         List<Integer> list = new ArrayList<Integer>();
//         for (int i = lo; i <= hi; ++i) {
//             list.add(i);
//         }
//         // 这里耗费时间太多
//         Collections.sort(list, (v1, v2) -> getWeight(v1) - getWeight(v2));
//         return list.get(k - 1);

        // 用队列进行排序
        // 按权重从大到小排序
        PriorityQueue<int[]> q = new PriorityQueue<>((v1, v2) -> v1[1] == v2[1] ? Integer.compare(v2[0], v1[0]) : Integer.compare(v2[1], v1[1]));
        for (int i = lo; i <= hi; ++i) {
            int w = getWeight(i);
            if (q.size() == k) { // 如果数量达到k，那么与第一个值进行比较
                // 如果小于了第一个值, 要把最大的退出，新的加入
                if (w < q.peek()[1]) {
                    q.poll();
                    q.offer(new int[]{i, w});
                }
            } else {
                q.offer(new int[]{i, w});
            }
        }
        // 返回队列的第一个元素
        return q.peek()[0];
    }

    private int getWeight(int num) {
        int cnt = 0;
        while (num != 1) {
            if (num % 2 == 0) {
                num /= 2;
            } else {
                num = num * 3 + 1;
            }
            cnt++;
        }
        return cnt;
    }
}
